package 力扣;

import java.util.ArrayList;

/**
 例如，给定二叉树

   1
  / \
  2   5
 / \   \
 3   4   6
 将其展开为：

 1
  \
    2
     \
      3
      \
      4
       \
        5
        \
         6
 */

public class _114二叉树展开为链表 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
        //将二叉树展开为单链表之后，单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。
        //因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构，
        // 因此在前序遍历结束之后将每个节点的左节点置空,留下右节点，将二叉树展开为单链表。

        public void flatten(TreeNode root) {
            ArrayList<TreeNode> list = new ArrayList<>();
            preOrder(root,list);
            //从1开始,每次遍历处理前一个节点
            for (int i = 1; i < list.size(); i++) {
                TreeNode pre = list.get(i - 1);
                TreeNode cur = list.get(i);
                pre.left = null;
                pre.right = cur;
            }
        }

        private void preOrder(TreeNode root, ArrayList<TreeNode> list) {
            if( root ==null) return;
            list.add(root);
            preOrder(root.left,list);
            preOrder(root.right,list);
        }
    }
}
